package BNS.graphs;

import java.io.PrintStream;
import java.io.Serializable;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.Vector;

/**
 * implements a general undirected graph notion, including a layout for each
 * node on the plane. Each Graph can have one of its Nodes designated as an
 * eigenNode, which is used in the construction of graphlets. Graphlets are
 * subgraphs of some other graph and reflect just those parts of the larger
 * graph that are defined as visible to a single player.
 */
public class Graph implements Serializable {
  private static final long serialVersionUID = 01L;

  private static final int NEIGHBOR_EDGES_FLAG = 0x2;
  private static final int NEIGHBOR_DEGREE_FLAG = 0x1;
  private static final int NEIGHBOR_PLUS_LABELING_FLAG = 0x4;
  private static final int SECOND_DEGREE_VIEW_FLAG = 0x8;
  private static final int FULL_DEGREE_VIEW_FLAG = 0x10;
	private int flag;
  
  Vector<Node> nodes; public Vector<Node> getNodes() {return nodes;}
  Vector<Edge> edges; public Vector<Edge> getEdges() {return edges;}
  public Node eigenNode; // will be null unless this Graph is a graphlet of another one.
  private Node[] reverse; // used so getNode() will run in constant time

  public Graph(int nNodes, int nEdges,int flag) {
  	this.flag=flag;
    nodes = new Vector<Node>(nNodes);
    edges = new Vector<Edge>(nEdges);
    eigenNode = null;
  }
  
  public Graph(int nNodes,int nEdges) {
  	this(nNodes,nEdges,0);
  }

  /** indicates this Graph is a graphlet of another (larger) graph */
  public boolean partial() {
    return eigenNode != null;
  }

  /** adds a Node to this graph with the given label and a unique index. */
  // @SuppressWarnings("unchecked")
  public Node addNode(String lbl) {
    reverse = null;
    Node n = new Node(lbl, nodes.size());
    nodes.addElement(n);
    return n;
  }

  /**
   * adds a Node to this graph with the same label and index as the given node.
   * Useful when making graphlets. TODO: make private?
   * 
   * @param node
   *          the Node whose label and index will be copied.
   */
  public Node addNode(Node node) {
    reverse = null;
    Node n = new Node(node);
    nodes.addElement(n);
    return n;
  }

  /**
   * returns the Node that has the index given. The index is a number that is
   * unique in the master graph; any graphlet constructed from it should have
   * nodes whose echos all have the same index as the original node in the
   * master. There is a performance penalty paid after new nodes are added to
   * the graph, but only once. As long as no more new nodes are added, this runs
   * in O(1) time.
   * 
   * @param idx
   *          the index of the sought-after node
   * @return the Node with index idx
   */
  public Node getNode(int idx) {
    if (reverse == null)
      buildReverse();
    return reverse[idx];
  }

  /** This constructs a datastructure to make getNode() run in constant time. */
  private void buildReverse() {
    Enumeration<Node> eno = enumNodes();
    Node n = eno.nextElement();
    int small = n.getIndex(), large = small;
    while (eno.hasMoreElements()) {
      int idx = eno.nextElement().getIndex();
      if (idx < small)
        small = idx;
      if (idx > large)
        large = idx;
    }
    // System.err.print("building reverse index, range "+ small +"<-->"+ large);

    reverse = new Node[large + 1];
    eno = enumNodes();
    while (eno.hasMoreElements()) {
      n = eno.nextElement();
      reverse[n.getIndex()] = n;
    }
    // System.err.print(" [");
    // for (int i=0; i<reverse.length; i++) System.err.print(" "+ reverse[i]);
    // System.err.println(" ]");
  }

  /**
   * Add an edge to a graph, but only if it does not already exist. Multiple
   * edges are not supported, but not for fundamental reasons; they are excluded
   * as a convenience because the initial graphs we wanted were all simple
   * graphs.
   */
  // @SuppressWarnings("unchecked")
  public synchronized Edge addEdge(Node nf, Node nt, boolean graphlet) {
    Enumeration<Edge> enumE = enumEdges();
    while (enumE.hasMoreElements()) {
      Edge e = enumE.nextElement();
      if (e.from == nf && e.to == nt || e.to == nf && e.from == nt)
        return null;
    }
    Edge newe = new Edge(nf, nt);
    edges.addElement(newe);
    if(!graphlet){ nf.addOutDegree(1);nt.addInDegree(1); }
    return newe;
  }
  
  public synchronized Edge addEdge(Node nf, Node nt) {
    return addEdge(nf,nt,false);
  }

  // public Edge addEdge(int f, int t) {
  // return addEdge(getNode(f),getNode(t));
  // }

  /** returns the number of nodes in a Graph. */
  public int numNodes() {
    return nodes.size();
  }

  /** returns the number of edges in a Graph. */
  public int numEdges() {
    return edges.size();
  }

  /** returns an Enumeration of all nodes in a Graph. */
  public Enumeration<Node> enumNodes() {
    return nodes.elements();
  }

  /** returns an Enumeration of all edges in a Graph. */
  public Enumeration<Edge> enumEdges() {
    return edges.elements();
  }

  /**
   * Calculates whether a graph is well colored or not. I.E. whether every node
   * has a (non-white) color, and every edge has a different color at both ends.
   * The argument should be true for this. To find out if a graph is colored the
   * same everywhere, the argument should be false. TODO: move this method to an
   * extension of Graph.
   * 
   * @param diff
   *          whether edges need to have different colors or not.
   */
  public boolean colored(boolean diff) {
    Enumeration<Edge> enEdges = enumEdges();
    while (enEdges.hasMoreElements()) {
      Edge edge = enEdges.nextElement();
      Node fr = edge.from;
      Node to = edge.to;
      if (fr.color != to.color ^ diff)
        return false;
    }
    Enumeration<Node> enNodes = enumNodes();
    //System.err.print("colored? checking: ");
    while (enNodes.hasMoreElements()) {
      Node node = enNodes.nextElement();
      //System.err.print("  " + node + ":" + node.color);
      if (node.color == 0)
        return false;
    }
    //System.err.println();
    return true;
  }

  /**
   * Calculates whether a graphlet is well-colored or not. I.E. whether every
   * node has a (non-white) color, and every edge has a different color at both
   * ends. The argument should be true for this calculation. To find out if a
   * graph is colored the *same* everywhere, the argument should be false. TODO:
   * move this method to an extension of Graph.
   * 
   * @param diff
   *          whether edges need to have different colors or not.
   */
  public boolean locallySolved(boolean diff, int[] state) {
    assert (eigenNode != null); // does not work on master graphs!
    Enumeration<Edge> enEdges = enumEdges();
    while (enEdges.hasMoreElements()) {
      Edge edge = enEdges.nextElement();
      Node fr = edge.from;
      Node to = edge.to;
      if (fr != eigenNode && to != eigenNode)
        continue; // Ignore nhbr-to-nhbr edges.

      // Can't use node's .color field because the copy of the graphlet sitting
      // at the
      // server is not being updated with colorbutton changes; use state
      // instead:
      if (state[fr.getIndex()] != state[to.getIndex()] ^ diff)
        return false;
    }
    Enumeration<Node> enNodes = enumNodes();
    // System.err.print("colored? checking: ");
    while (enNodes.hasMoreElements()) {
      Node node = enNodes.nextElement();
      // System.err.print(" "+node.ID+":"+node.color);
      // Can't use node's .color because the copy of the graphlet sitting at the
      // server is not being updated with colorbutton changes; use state
      // instead:
      if (state[node.getIndex()] == 0)
        return false;
    }
    // System.err.println();
    return true;
  }

  /**
   * tests to see if a node has a different color from all its neighbours. TODO:
   * move this method to an extension of Graph.
   * 
   * @param node
   *          the node to test
   * @return true iff it has no neighbours with the same color.
   */
  public boolean unlike(Node node) {
    Enumeration<Edge> enEdges = enumEdges();
    while (enEdges.hasMoreElements()) {
      Edge edge = enEdges.nextElement();
      Node fr = edge.from;
      Node to = edge.to;
      if (to != node && fr != node)
        continue;
      if (fr.color == to.color)
        return false;
    }
    return true;
  }

  /**
   * Counts the number of edges in a graph that are satisfactorily colored. If
   * flag is true, then it counts edges that have a different color at both
   * ends. If flag is false, then it counts edges that have the same color at
   * both ends. TODO: move this method to an extension of Graph.
   * 
   * @param flag
   *          determines if neighbours should be different or the same
   */
  public int satEdges(boolean flag) {
    int numSatisfied = 0;
    Enumeration<Edge> enEdges = enumEdges();
    while (enEdges.hasMoreElements()) {
      Edge edge = enEdges.nextElement();
      Node fr = edge.from;
      Node to = edge.to;
      if (to.color == 0 || fr.color == 0)
        continue;
      if ((fr.color == to.color) ^ flag)
        numSatisfied++;
      // System.err.print(numSatisfied +" ");
    }
    // System.err.println("sat'ed");
    return numSatisfied;
  }

  /**
   * Counts the number of edges in a graph that are satisfactorily matched. A
   * match is present if the nodes on either end declare their sweety's to be
   * each other. TODO: move this method to an extension of Graph.
   */
  public int countMatches() {
    int numMatched = 0;
    Enumeration<Edge> enEdges = enumEdges();
    while (enEdges.hasMoreElements()) {
      Edge edge = enEdges.nextElement();
      Node fr = edge.from;
      Node to = edge.to;
      if (to.getSweety() == fr && fr.getSweety() == to)
        numMatched++;
      // System.err.print(numMatched +" ");
    }
    // System.err.println("sat'ed");
    return numMatched;
  }

  /**
   * Finds and returns the node whose position in the layout is closest to
   * (x,y).
   * 
   * @param x
   *          the horizontal coordinate of the point of interest.
   * @param y
   *          the vertical coordinate of the point of interest.
   */
  public Node select(int x, int y) {
    double bestdist = Double.MAX_VALUE;
    Node pick = null;
    Enumeration<Node> eno = enumNodes();
    while (eno.hasMoreElements()) {
      Node n = eno.nextElement();
      double dist = (n.x - x) * (n.x - x) + (n.y - y) * (n.y - y);
      // System.err.println(n +" @("+ n.x +", "+ n.y +") dist="+ dist);
      if (dist < bestdist) {
        bestdist = dist;
        pick = n;
      }
    }
    return pick;
  }

  /**
   * Finds and returns the node in the graph whose position relative to a given
   * node is at an angle closest to the angle from the given node to a given
   * point of interest.
   * 
   * @param me
   *          the given Node
   * @param x
   *          the horizontal coordinate of the point of interest.
   * @param y
   *          the vertical coordinate of the point of interest.
   */
  public Node selectNeighbour(Node me, int x, int y) {
    double pickAngle = Math.atan2(y - me.y, x - me.x);
    // System.err.println("searching for neighbour of "+me+" at "+x+","+y+"
    // angle="+pickAngle);
    double diffAngle = Double.MAX_VALUE;
    Node pick = null;
    Enumeration<Node> eno = enumNodes();
    while (eno.hasMoreElements()) {
      Node n = eno.nextElement();
      if (n == me)
        continue;
      double nodeAngle = Math.atan2(n.y - me.y, n.x - me.x);
      // System.err.println("neighbour "+n+" at "+n.x+","+n.y+"
      // angle="+nodeAngle);
      double diff = Math.abs(nodeAngle - pickAngle);
      if (diff > Math.PI)
        diff = 2 * Math.PI - diff;
      if (diff < diffAngle) {
        pick = n;
        diffAngle = diff;
      }
    }
    return pick;
  }

  /**
   * Prints the layout of Graph on a given PrintStream.
   * 
   * @param prstr
   *          the stream where the data will appear.
   */
  public void printLayout(PrintStream prstr) {
    prstr.println("graph " + this + "\nhas " + numNodes() + " nodes");
    Enumeration<Node> enu = enumNodes();
    String punct = "{";
    while (enu.hasMoreElements()) {
      Node n = enu.nextElement();
      prstr.print(punct + n.getIndex() + "->{" + n.x + "," + n.y + "}");
      punct = ", ";
    }
    prstr.println("}");
  }

  /**
   * Prints a representation of a whole Graph on a given PrintStream.
   * 
   * @param prstr
   *          the stream where the data will appear.
   */
  public void prettyPrint(PrintStream prstr) {
    int total = 0;
    prstr.println("graph " + this + "\nhas these " + numEdges() + " edges");
    Enumeration<Edge> enu = enumEdges();
    while (enu.hasMoreElements()) {
      Edge e = enu.nextElement();
      prstr.print(" " + e);
    }
    prstr.println("\nand these " + numNodes() + " nodes");
    Enumeration<Node> enuN = enumNodes();
    while (enuN.hasMoreElements()) {
      Node n = enuN.nextElement();
      if (n == eigenNode)
        prstr.print("eigenNode");
      prstr.println(" " + n + " [" + n.getIndex() + "]\t\t" + n.inDegree + "+"
          + n.outDegree + "\t=" + (n.degree()));
      total += (n.degree());
    }
    prstr.println("\t\t\t" + total);
  }

  /**
   * Prints a histogram of each degree in this Graph. The "degree" is the sum of
   * inDegree() and outDegree().
   * 
   * @param prstr
   *          the PrintStream where the data will appear.
   */
  public void histoDegrees(PrintStream prstr) {
    int[] hist = new int[numNodes()];
    Enumeration<Node> eno = enumNodes();
    while (eno.hasMoreElements()) {
      Node n = eno.nextElement();
      hist[n.inDegree + n.outDegree]++;
    }
    int i = numNodes() - 1;
    while (i >= 0 && hist[i] == 0) {
      // prstr.println(i+"\t"+hist[i]);
      i--;
    }
    while (i >= 0) {
      if (hist[i] > 0)
        prstr.println(i + "\t" + hist[i]);
      // for(int h=hist[i]; h>0; h--) System.err.print("*");
      // prstr.println(" "+ hist[i]);
      i--;
    }
  }

  /**
   * creates a subgraph defined by a given Node and all its neighbours in the
   * current Graph. The defining node in the new graph is designated as the
   * eigenNode. Copies of all nodes are created for the new subgraph; there is
   * no enduring connection between the old and the new. The edges between the
   * eigen node and its neighbours are also included, but no other edges
   * (specifically those between the non-eigen nodes), unless extras>0 .
   * 
   * @param focus
   *          the Node that will be echoed as the eigenNode of the new graphlet Graph.
   * @param extras
   *          an integer indicating the makeup of the graphlet.
   */
  public Graph makeGraphlet(Node focus, int flag) {
    Graph newg = new Graph(10,10,flag);
    Hashtable<Node, Node> ht = new Hashtable<Node, Node>(); // map from node in
    Hashtable<Node, Node> ht2 = new Hashtable<Node, Node>();
    // old graph to its
    // mirror in new
    // graph
    Node eigen = newg.addNode(focus);
    newg.eigenNode = eigen;
    ht.put(focus, eigen);


    Enumeration<Edge> enumE = this.enumEdges();
    
    if(newg.isFullDegreeViewOn()) {
      while (enumE.hasMoreElements()) {
        Edge e = enumE.nextElement();

        Node newTo = ht.get(e.to);
        Node newFm = ht.get(e.from);
        
        if((newTo=ht.get(e.to)) == null)
          ht.put(e.to, newTo=newg.addNode(e.to));
        if((newFm=ht.get(e.from)) == null)
          ht.put(e.from, newFm=newg.addNode(e.from));
        newg.addEdge(newFm, newTo, true);
      }
    }
    else {
    
    // first: search for neighbours & mirror each node
    while (enumE.hasMoreElements()) {
      Edge e = enumE.nextElement();
      if (e.to == focus) {
        if (ht.get(e.from) != null)
          System.err.println("multiple edge found: " + e);
        else {
          Node n = newg.addNode(e.from);
          ht.put(e.from, n);
          newg.addEdge(eigen,n,true);
        }
      }
      if (e.from == focus) {
        if (ht.get(e.to) != null)
          System.err.println("multiple edge found: " + e);
        else {
          Node n = newg.addNode(e.to);
          ht.put(e.to, n);
          newg.addEdge(eigen,n,true);
        }
      }
    }

    // second: mirror all edges between neighbours
    enumE = this.enumEdges();
    
    /*while (enumE.hasMoreElements()) {
    Edge e = enumE.nextElement();
    Node newTo = ht.get(e.to);
    Node newFm = ht.get(e.from);
    if (e.to == focus || e.from == focus || 
       (isFlagOn(NEIGHBOR_EDGES_FLAG,extras) && newTo != null && newFm != null)) {
      // this edge needs to be echoed
      newg.addEdge(newFm, newTo);
    }
    if(isFlagOn(NEIGHBOR_DEGREE_FLAG,extras)) {
      //if (newTo == null && newFm != null) newFm.otherEdges++;
      if(newFm != null && (newTo == null || !isFlagOn(NEIGHBOR_PLUS_LABELING_FLAG,extras)))
        newFm.otherEdges++;

      if(newTo != null && (newFm == null || !isFlagOn(NEIGHBOR_PLUS_LABELING_FLAG,extras)))
    //if (newTo != null && newFm == null)
        newTo.otherEdges++;}
  }*/

    /**
     * Second degree view
     * 
     */

    if(newg.isSecondDegreeViewOn()) {

      while (enumE.hasMoreElements()) {
        Edge e = enumE.nextElement();
        Node newTo = ht.get(e.to);
        Node newFm = ht.get(e.from);

        if (newTo != null) {
          if(newFm == null && (newFm=ht2.get(e.from))==null) 
            ht2.put(e.from,newFm=newg.addNode(e.from));
          
        	newg.addEdge(newFm,newTo,true);
        }
        else if(newFm != null) {
          if((newTo=ht2.get(e.to))==null) 
            ht2.put(e.to,newTo=newg.addNode(e.to));
          
        	newg.addEdge(newFm,newTo,true);
        }
      }
    }   
    }
     /*   if (e.to == focus || e.from == focus
            || (isFlagOn(NEIGHBOR_EDGES_FLAG, extras) && newTo != null && newFm != null)) {
          // this edge needs to be echoed
          newg.addEdge(newFm, newTo);
        }
      if (isFlagOn(NEIGHBOR_DEGREE_FLAG, extras)) {
        // if (newTo == null && newFm != null) newFm.otherEdges++;
        if (newFm != null
            && (newTo == null || !isFlagOn(NEIGHBOR_PLUS_LABELING_FLAG, extras)))
          newFm.otherEdges++;

        if (newTo != null
            && (newFm == null || !isFlagOn(NEIGHBOR_PLUS_LABELING_FLAG, extras)))
          // if (newTo != null && newFm == null)
          newTo.otherEdges++;
      }
    }*/

    /**
     * End of second degree view
     * 
     */

    return newg;
  }

  /*private boolean isFlagOn(int flag, int extras) {
    return (flag & extras) == flag;
  }*/
  
  public boolean isNeighborDegreeOn() {
  	return((NEIGHBOR_DEGREE_FLAG&flag)==NEIGHBOR_DEGREE_FLAG);
  }

	public boolean isPlusLabelingOn() {
  	return((NEIGHBOR_PLUS_LABELING_FLAG&flag)==NEIGHBOR_PLUS_LABELING_FLAG);
	}
	
	public boolean isNeighborEdgesOn() {
  	return((NEIGHBOR_EDGES_FLAG&flag)==NEIGHBOR_EDGES_FLAG);
	}	
  
  public boolean isSecondDegreeViewOn() {
    return((SECOND_DEGREE_VIEW_FLAG&flag)==SECOND_DEGREE_VIEW_FLAG);
  } 
  
  public boolean isFullDegreeViewOn() {
    return((FULL_DEGREE_VIEW_FLAG&flag)==FULL_DEGREE_VIEW_FLAG);
  } 
	
	

  /*
   * public static void main(String[] args) { int nNodes=5; if(args.length>0)
   * nNodes= Integer.parseInt(args[0]); System.err.println("building ring graph
   * of size "+ nNodes); Graph gr= new Graph(nNodes,nNodes); for(int i=1; i<=nNodes;
   * i++) gr.addNode(""+i); // for(int e=1; e<nNodes; e++) gr.addEdge(e,e+1); //
   * gr.addEdge(nNodes,1); gr.prettyPrint(System.err);
   * gr.makeGraphlet(0,2).prettyPrint(System.err); }
   */
}
